/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  if (nums.length <= 1) return nums
  let mid = Math.floor(nums.length / 2) // 取出中间位置
  let left = nums.slice(0, mid)
  let right = nums.slice(mid)
  return merge(sortArray(left), sortArray(right))
};
function merge (left, right) {
  let res = []
  let i = 0
  let j = 0
  let m = left.length
  let n = right.length
  while (i < m && j < n) {
    if (left[i] < right[j]) {
      res.push(left[i++])
    } else {
      res.push(right[j++])
    }
  }
  while (i < m) {
    res.push(left[i++])
  }
  while (j < n) {
    res.push(right[j++])
  }
  return res
}
let arr = [1, 8, 9, 5, 10, 3, 6, 2, 8, 21, 13]
console.log(sortArray(arr));